package br.com.rookgraph.branchreduce;

import br.com.rookgraph.Edge;
import br.com.rookgraph.Graph;
import br.com.rookgraph.heuristica.Heuristica;
import br.com.rookgraph.utils.ArrayUtils;


/**
 * Implementação do Algoritimo de IR. Extraido do artigo: "Abordagem de
 * Refinamento interativo para o problema da árvore geradora com número mínimo
 * de vertices Branches." - Diego Mello da Silva
 *
 *
 * @author Luan Pontes
 * @since 5-10-12
 *
 */
public class BranchReduce {

	private Graph original;
	private Graph tree;
	private Heuristica heuristica;

	public BranchReduce(Graph original, Graph tree, Heuristica heuristica) {
		super();
		this.original = original;
		this.tree = tree;
		this.heuristica = heuristica;
	}

	public Graph execute() {

		Graph graphBest = this.tree;
		boolean replaceEdge;
		
		do {
			replaceEdge = false;

			Edge[] listCut = createCuttingList();

			Edge[] listRep;
			while (!replaceEdge && listCut.length != 0) {

				Edge edgeCut = selectCutEdge(listCut);

				this.tree.removeEdge(edgeCut);

				listCut = ArrayUtils.removeEdgeList(edgeCut, listCut);

				listRep = createReplacementListToCuttingEdge(edgeCut);

				Edge replace = selectEdgeFromReplamentList(listRep, edgeCut);

				if (replace != null) {	

					this.tree.addEdge(replace);

					replaceEdge = true;

					if (isTreeBest(graphBest)) {

						try {
							graphBest = (Graph) this.tree.clone();
						} catch (CloneNotSupportedException e) {
							e.printStackTrace();
						}
					}

				} else {

					this.tree.addEdge(edgeCut);

				}
			}
		} while (replaceEdge);
		return graphBest;
	}

	public boolean isTreeBest(Graph graphBest) {
		return this.tree.getBranchs().length < graphBest.getBranchs().length;
	}

	/**
	 * Seleciona dentre as candidatas a melhor aresta para coste.
	 * Com base na heuristica usada.
	 * Retorn null se a lista vinher vazia.
	 *
	 * @param listRep
	 * @return
	 */
	protected Edge selectCutEdge(final Edge[] listCut) {

		Edge edgeCut = null;
		for (Edge candidate : listCut) {

			edgeCut = this.heuristica.selectForCut(candidate, edgeCut);

		}
		return edgeCut;
	}

	/**
	 * Seleciona dentre as candidatas a melhor aresta para Substituição,.
	 * Com base na heuristica usada.
	 * Retorn null se a lista vinher vazia, ou a aresta selecionada não for
	 * vantajosa sobre a aresta de cut.
	 *
	 * @param listRep
	 * @param edgeCut
	 * @return
	 */
	protected Edge selectEdgeFromReplamentList(final Edge[] listRep, Edge edgeCut) {

		Edge edgeRep = null;
		
	
		for (Edge candidate : listRep) {
			
			// estava aki
			
			edgeRep = this.heuristica.selectForRep(candidate, edgeRep);

		}
		
		return (edgeRep != null && this.heuristica.isVantajoso(edgeRep, edgeCut))? edgeRep : null;
	}

	public void calcParameters(Edge edge, boolean insert) {
		if(edge != null){
			edge.alfa = this.tree.alfa(edge);
			edge.sigma = this.tree.sigma(edge);

			/* Só pra ganhar um pouco de despenho  =) */
//			if(this.heuristica instanceof Plus){
				edge.beta = this.tree.beta(edge, insert);
				edge.gama = this.tree.gama(edge, insert);
				edge.sigmaLine = this.original.sigma(edge);
//			}
		}
	}

	protected Edge[] createReplacementListToCuttingEdge(final Edge arestaCut) {

		int[] seg1 = this.tree.reached(arestaCut.origin, new int[this.tree.getOrder()]);
		int[] seg2 = this.tree.reached(arestaCut.target, new int[this.tree.getOrder()]);

		// TODO verificar tamanho dessa lista por um teorema.
		Edge[] arestasRep = new Edge[seg1.length * seg2.length];

		int count = 0;

		/* Comparar arestas dos segmentos com as do grafo original */
		for (int vSeg1 : seg1) {
			for (int vSeg2 : seg2) {

				final Edge currentArest = new Edge(vSeg1, vSeg2);

				// if (!currentArest.equals(arestaCut) {  na heuritisca original a linha é essa
				if (!currentArest.equals(arestaCut) && (this.original.grau(vSeg1) > 1 && this.original.grau(vSeg2) > 1)) {

					if (!this.tree.hasEdge(vSeg1, vSeg2) && this.original.hasEdge(vSeg1, vSeg2)) {
                        
						//  veio para cá
						
					    this.tree.addEdge(currentArest);

						calcParameters(currentArest, true);

						this.tree.removeEdge(currentArest);

						arestasRep[count++] = currentArest;
					}
				}
			}
		}

		Edge[] listRep = new Edge[count];
		System.arraycopy(arestasRep, 0, listRep, 0, count);

		return listRep;
	}

	/**
	 * Cria a lista de arestas candidatas a corte.
	 *
	 * @return
	 */
	protected Edge[] createCuttingList() {
		int order = tree.getOrder();
		int count = 0;
		Edge[] edgesCut = new Edge[order * order];

		for (int branch : this.tree.getBranchs()) {
			for (int adjacente : this.tree.getAdjacentes(branch)) {

				Edge candidata = new Edge(branch, adjacente);

				// if (!conteins(candidata, edgesCut)) { na algoritimo original a linha é essa
				if (!ArrayUtils.conteins(candidata, edgesCut)  && (this.original.grau(adjacente) > 1)){
					calcParameters(candidata, false);
					edgesCut[count++] = candidata;
				}
			}
		}

		Edge[] listCut = new Edge[count];
		System.arraycopy(edgesCut, 0, listCut, 0, count);
		return listCut;
	}


	public Graph getOriginal() {
		return original;
	}

	public void setOriginal(Graph original) {
		this.original = original;
	}

	public Graph getTree() {
		return tree;
	}

	public void setTree(Graph tree) {
		this.tree = tree;
	}

}